# 凑零钱问题 dptable

def coinChange(coins, amount):
    # 数组⼤⼩为 amount + 1，初始值也为 amount + 1
    dp = [amount + 1 for i in range(0, amount + 1)]
    print(dp)
    # base
    dp[0] = 0
    for i, v in enumerate(dp):
        # 内层 for 在求所有⼦问题 + 1 的最⼩值
        for j, v2 in enumerate(coins):
            # 子问题无解跳过
            if i - v2 < 0:
                continue
            dp[i] = min(dp[i], 1 + dp[i - v2])

    # amount+1 代表正无穷
    return -1 if dp[amount] == amount + 1 else dp[amount]


if __name__ == '__main__':
    a = [1, 2, 5]
    b = coinChange(a, 11)
    print(b)
